// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。


#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
// 看了题解
// 执行用时：
// 8 ms
// , 在所有 C++ 提交中击败了
// 90.87%
// 的用户
// 内存消耗：
// 7.6 MB
// , 在所有 C++ 提交中击败了
// 74.98%
// 的用户

class Solution {
public:
    string minWindow(string s, string t) {
        // z的ascii为122
        vector<int> hash(123);
        int left=0,right=0,minlen=INT_MAX,minstart=0,need=t.size();
        for(auto c:t){
            hash[c]++;
        }
        while(right<s.size()){
            // 向右扩大
            if(hash[s[right]]>0){
                need--;
            }
            hash[s[right]]--;
            right++;
            // 向右缩小
            while(need==0){
                if(right-left<minlen){
                    minlen=right-left;
                    minstart=left;
                }
                // 此处任意一个向右缩小都++，因为前面任意字符都--，非t中字符均为负数，就算全部排除非t中字符，最多为0，所以>0的必为t中字符
                hash[s[left]]++;
                if(hash[s[left]]>0){
                    need++;
                }
                left++;

            }
        }
        if(minlen!=INT_MAX){
            return s.substr(minstart,minlen);
        }
        else{
            return "";
        }

    }
};